package com.sicheng.algorithm.string;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/4/14 16:26
 */
public class 后缀表达式 {

    public static void main(String[] args) {
        System.out.println(backPrefix("2*(9+6/3-5)+4"));
    }

    //中缀转后缀表达式
    // ( 直接入栈
    // 数字直接输出
    // ) 栈中元素依次输出，遇到(抵消
    // 符号  优先级高直接入栈， 否则输出栈顶
    public static Deque<Character> backPrefix(String s) {
        StringBuilder path = new StringBuilder();
        ArrayDeque<Character> res = new ArrayDeque<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(')
                path.append('(');
            else if (c >= '0' && c <= '9')
                res.addLast(c);
            else if (c == ')') {
                while (path.charAt(path.length() - 1) != '(') {
                    res.addLast(path.charAt(path.length() - 1));
                    path.deleteCharAt(path.length() - 1);
                }
                path.deleteCharAt(path.length() - 1);
            } else {
                if (path.length() > 0 && path.charAt(path.length() - 1) != '(') {
                    while (path.length() > 0 && !isHigh(c, path.charAt(path.length() - 1))) {
                        res.addLast(path.charAt(path.length() - 1));
                        path.deleteCharAt(path.length() - 1);
                    }
                }
                path.append(c);
            }
        }

        if (path.length() > 0)
          res.addLast(path.charAt(0));
        return res ;
    }

    public static boolean isHigh(char op1, char op2) {
        return getPriority(op1) > getPriority(op2);
    }

    public static int getPriority(char op) {
        if (op == '+' || op == '-')
            return 0;
        if (op == '*' || op == '/')
            return 1;
        return -1;
    }

}
